#include <bits/stdc++.h>

using namespace std;

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
vector<string> generateParenthesis(int n);
void dfs(int left, int right);

int main()
{
	return 0;
}

string layer;
vector<string> res;
vector<string> generateParenthesis(int n)
{
	dfs(n, n);
	return res;
}

void dfs(int left, int right)
{
	if (!left && !right) {
		res.emplace_back(layer);
		return;
	}
	if (left > 0) {
		layer.push_back('(');
		dfs(left - 1, right);
		layer.pop_back();
	}
	if (left < right) {
		layer.push_back(')');
		dfs(left, right - 1);
		layer.pop_back();
	}
}
